﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// BIT
    /// 1~i 의 총합을 구할 수 있음
    /// O(log n)
    /// </summary>
    class BinaryIndexedTree
    {
        int[] bit;
        int n;
        public BinaryIndexedTree(int maxSize)
        {
            bit = new int[maxSize + 1];
            n = maxSize;
        }
        /// <summary>
        /// 0부터 i까지의 합을 구함
        /// </summary>
        public int Sum(int i)
        {
            int s = 0;
            while (i > 0)
            {
                s += bit[i];
                i -= i & -i;
            }
            return s;
        }
        /// <summary>
        /// i번째 값에 x를 더함
        /// </summary>
        public void Add(int i, int x)
        {
            while (i <= n)
            {
                bit[i] += x;
                i += i & -i;
            }
        }
    }
}
